The present invention relates to more efficient techniques for performing calculations for determining error locations, and more particularly, to techniques for determining error locations in data by performing Galois field logarithm calculations that require less storage space.
Arithmetic operations performed in Galois field are important in numerous applications. A Galois field GF(2m) is a set that contains a finite number of elements, where m is a positive integer. The elements of a Galois field can be represented in many ways.
One application involves using Galois field arithmetic to determine the location of errors in digital data. One such example are Reed-Solomon codes that are used in hard disk drives, compact disk players, communications systems, and in other applications. Most of these applications require fast methods or simple integrated circuits that perform operations such as multiplication, squaring, addition, and exponentiation.
The calculation of 16-bit finite fields is required to determine the location of errors in digital data using Reed-Solomon error correction encoding techniques. This operation involves a 16-bit finite logarithm calculation using Galois field arithmetic. The operation can be performed using circuitry or software by storing all possible output values of the 16-bit logarithm in a lookup table. The table for the 16-bit logarithm has 16(216−1)=1,048,560 values. An implementation of a table of this size requires about one million logic gates.
Therefore, it would be desirable to provide techniques for reducing the amount of bits stored in tables that represent a 16-bit finite Galois field logarithm calculation.